import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }

    /**
     * 选择排序
     * @param arr
     */
    public static void selectSort(int[] arr){
        if(arr == null || arr.length <2){
            return;
        }
        Arrays.sort(arr);
        for (int i =0;i<arr.length-1;i++){
            int minIndex = i;
            for (int j = i+1;j<arr.length;j++){
                minIndex = arr[j]<arr[minIndex]?j:minIndex;
            }
            swapNormal(arr,minIndex,i);
        }
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        if (arr == null || arr.length <2){
            return;
        }
        for (int i =arr.length-1;i>0;i--){
            if (arr[i]>arr[i+1]){
                swapUnNormal(arr,i,i+1);
            }
        }
    }

    /**
     * 正常交换
     * @param arr
     * @param i
     * @param j
     */
    public static void swapNormal(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 使用异或运算交换数组中两个位置的数
     * 条件：i 不等于j
     * @param arr
     * @param i
     * @param j
     */
    public static void swapUnNormal(int[] arr,int i,int j){
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }

    /**
     * 有一组数，其中只有一种数出现奇数次，其他所有数都出现偶数次，求这个出现奇数次的数。
     * 异或运算法则：相同为0，不同为1
     * 1）0^N=N N^N=0
     * 2）符合交换率和结合率
     * @param arr
     */
    public static void yiHuoExe(int[] arr){
        int eor = 0;
        for (int cur : arr){
            eor ^= cur;
        }
        System.out.println(eor);
    }

    /**
     * 有一组数，其中只有两种数是出现奇数次的，其他所有数都是偶数次，求这两个出现奇数次的数。
     * 异或运算法则：相同为0，不同为1
     * 1）0^N=N N^N=0
     * 2）符合交换率和结合率
     * @param arr
     */
    public static void yiHuoExe2(int[] arr){
        int eor = 0;
        for (int cur : arr){
            eor ^= cur;
        }
        int onlyOne = 0;
        int rightOne = eor + (~eor+1);
        for (int cur:arr){
            if ((cur & rightOne) == 0){
                onlyOne ^= cur;
            }
        }
        System.out.println(onlyOne + "" + (onlyOne^eor));
    }

    public static void insertSort(int[] arr){
        if (arr == null || arr.length <2){
            return;
        }
        for (int i=1;i<arr.length;i++){
            for (int j=i-1;j>=0 && arr[j]>arr[j+1];j--){
                swapUnNormal(arr,j,j+1);
            }
        }
    }
}